Vorzeitige Konvergenz

Bei evolutionären Algorithmen (EA) bedeutet der Begriff der vorzeitigen Konvergenz, dass die Individuen (= Lösungen eines Optimierungsproblems) einer Population zu einem Suboptimum konvergiert sind und sich somit alle Individuen im Suchraum am Suboptimum oder in seiner Nähe befinden. In einer solchen Situation sind die elterlichen Lösungen nicht mehr in der Lage, mit Hilfe der genetischen Operatoren Nachkommen zu erzeugen, die ihre Eltern übertreffen. Vorzeitige Konvergenz ist ein häufiges Problem bei evolutionären Algorithmen^[1] und geht mit dem Verlust einer großen Anzahl von Allelen einher. Ein Allel gilt als verloren, wenn in einer Population alle Individuen das gleiche Allel für ein Gen aufweisen. Demgegenüber wird ein Allel nach der etwas schwächeren Definition von De Jong als konvergentes Allel angesehen, wenn 95 % einer Population den gleichen Wert für ein bestimmtes Gen aufweisen.^[2] Trifft dies auf alle oder die meisten Chromosomen und ihre Gene in einer Population zu, kann der Rekombinationsoperator nicht mehr wirken, da die elterlichen Gene vollständig oder nahezu identisch sind. Änderungen sind dann nur noch durch Mutationsoperatoren möglich. Im Laufe einer solchen vorzeitigen Konvergenz wird es somit immer schwieriger, verloren gegangene und nützliche Allelwert wieder zu finden.^[3]^[4]

↑ A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). 2. Auflage. Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, Multimodal Problems, Selection, and the Need for Diversity, S. 91–98, doi:10.1007/978-3-662-44874-8.
↑ Kenneth A. De Jong: Analysis of the behavior of a class of genetic adaptive systems. Dissertation. University of Michigan, Ann Arbor, MI, USA 1975 (handle.net).
↑ Yee Leung, Yong Gao, Zong-Ben Xu: Degree of population diversity - a perspective on premature convergence in genetic algorithms and its Markov chain analysis. In: IEEE Transactions on Neural Networks. Band 8, Nr. 5, September 1997, ISSN 1045-9227, S. 1165–1176, doi:10.1109/72.623217 (ieee.org [abgerufen am 25. Oktober 2023]).
↑ James E. Baker: Adaptive Selection Methods for GeneticAlgorithms. In: John J. Grefenstette (Hrsg.): Proceedings of the First International Conference on Genetic Algorithms and their Applications (ICGA). L. Erlbaum, Hillsdale, NJ, USA 1985, ISBN 978-0-8058-0426-3, S. 101–111.

[:10-1] A.E. Eiben, J.E. Smith: Introduction to Evolutionary Computing (= Natural Computing Series). 2. Auflage. Springer, Berlin, Heidelberg 2015, ISBN 978-3-662-44873-1, Multimodal Problems, Selection, and the Need for Diversity, S. 91–98, doi:10.1007/978-3-662-44874-8.

[:3-2] Kenneth A. De Jong: Analysis of the behavior of a class of genetic adaptive systems. Dissertation. University of Michigan, Ann Arbor, MI, USA 1975 (handle.net).

[:0-3] Yee Leung, Yong Gao, Zong-Ben Xu: Degree of population diversity - a perspective on premature convergence in genetic algorithms and its Markov chain analysis. In: IEEE Transactions on Neural Networks. Band 8, Nr. 5, September 1997, ISSN 1045-9227, S. 1165–1176, doi:10.1109/72.623217 (ieee.org [abgerufen am 25. Oktober 2023]).

[:4-4] James E. Baker: Adaptive Selection Methods for GeneticAlgorithms. In: John J. Grefenstette (Hrsg.): Proceedings of the First International Conference on Genetic Algorithms and their Applications (ICGA). L. Erlbaum, Hillsdale, NJ, USA 1985, ISBN 978-0-8058-0426-3, S. 101–111.

[1]

[2]

[3]

[4]